#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    vector<int> maximizeXor(vector<int> &nums, vector<vector<int>> &queries) {
        sort(nums.begin(), nums.end());
        int Q = queries.size();
        int N = nums.size();
        for (int i = 0; i < Q; ++i)
            queries[i].push_back(i);
        sort(queries.begin(), queries.end(), [](const vector<int> &a, const vector<int> &b) {
            return a[1] < b[1];
        });
        vector<int> ans(Q);
        int i = 0;
        for (auto query:queries) {
            for (i; i < N && nums[i] <= query[1]; ++i) {
                trie.addNumber(nums[i]);
            }
            ans[query[2]] = trie.queryMaxXor(query[0]);
        }
        return ans;
    }

private:

    struct Node {
        Node(Node *_leftChild = nullptr, Node *_rightChild = nullptr) :
                leftChild(_leftChild),
                rightChild(_rightChild) {}

        Node *leftChild;
        Node *rightChild;
    };

    class Trie {
    public:
        Trie() : root(new Node()) {}

        void getBits(int bits[], unsigned int x) {
            for (int i = 0; i < 31; ++i) {
                bits[i] = x & 1;
                x >>= 1;
            }
        }

        void addNumber(int x) {
            int bits[31];
            getBits(bits, x);
            auto thisNode = root;
            for (int i = 30; i >= 0; --i) {
                if (bits[i]) {
                    thisNode->rightChild ? thisNode = thisNode->rightChild
                                         : thisNode = thisNode->rightChild = new Node();
                } else {
                    thisNode->leftChild ? thisNode = thisNode->leftChild
                                        : thisNode = thisNode->leftChild = new Node();
                }
            }
        }

        int queryMaxXor(int x) {
            if (!root->leftChild && !root->rightChild)return -1;
            int bits[31];
            getBits(bits, x);
            auto thisNode = root;
            int maxXor = 0;
            int tmp = 1 << 30;
            for (int i = 30; i >= 0; --i) {
                auto leftChild = thisNode->leftChild;
                auto rightChild = thisNode->rightChild;
                if (bits[i]) {
                    if (leftChild || !rightChild) {
                        thisNode = leftChild;
                        maxXor |= tmp;
                    } else thisNode = rightChild;
                } else {
                    if (rightChild || !leftChild) {
                        thisNode = rightChild;
                        maxXor |= tmp;
                    } else thisNode = leftChild;
                }
                tmp >>= 1;
            }
            return maxXor;
        }

    private:
        Node *root;
    } trie;

};

int main() {
    Solution solution;
    vector<int> nums = {5, 2, 4, 6, 6, 3};
    vector<vector<int>> queries = {
            {12, 4},
            {8,  1},
            {6,  3},

    };

    solution.maximizeXor(nums, queries);
}

